package _11_整理题目._2_二叉树_递归_dfs_bfs._递归;


import org.junit.Test;
import util.TreeNode;

/**
 *
 *
 * 给定彼此独立的两棵二叉树，判断 t1 树是否有与 t2 树拓扑结构完全相同的子树。
 * 设 t1 树的边集为 E1，t2 树的边集为 E2，
 * 若 E2 等于 E1 ，则表示 t1 树和t2 树的拓扑结构完全相同。
 * 
 * 由题意，t1 是包含 t2 的。
 * 方法一：递归
 * 
 * 
 * 方法二：中序遍历 + Strings.contains()
 *      
 * 
 */
public class _05_判断t1树中是否有与t2树拓扑结构完全相同的子树 {
    
    public boolean isContains1 (TreeNode root1, TreeNode root2) {
        if(root1 == null) return false;
        return isContains1(root1.left, root2) || isContains1(root1.right, root2) || isSubtree(root1, root2);
    }
    
    private boolean isSubtree(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return true;
        
        if(root1 == null || root2 == null || root1.val != root2.val) return false;
        
        return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
    }

    @Test
    public void main() {
        Integer[] input1 = {1, 2, 3, 4, 5, 6, 7, null, 8, 9};
        Integer[] input2 = {2, 4, 5, null, 8, 9};
        TreeNode root1 = TreeNode.getTreeFromArray(input1);
        TreeNode root2 = TreeNode.getTreeFromArray(input2);
        System.out.println(isContains1(root1, root2));
        System.out.println(isContains2(root1, root2));
    }

    public boolean isContains2 (TreeNode root1, TreeNode root2) {
        StringBuilder str1 = new StringBuilder();
        StringBuilder str2 = new StringBuilder();
        preOrder(root1, str1);
        preOrder(root2, str2);
        if (str1.toString().contains(str2.toString())) {
            return true;
        } else {
            return false;
        }
    }

    private void preOrder(TreeNode root, StringBuilder str) {
        if (root == null) return;
        preOrder(root.left, str);
        str.append(root.val);
        preOrder(root.right, str);
    }
}
